# Prim：搜索权重最小的邻边加入树中

from tools.Input import Input
from tools.Output import Output


class Prim:
    __name = 'Prim'

    @staticmethod
    def do_prim():
        # g = Input.input_graph()  # 输入无向图
        g = Input.get_graph1()  # 获取一个图（例3.2.1）
        print('输入的图为：')
        Output.print_graph_set(g)

        v_set = g[0]  # 图的点集
        s_set = g[1]  # 图的边集

        tv_set = []  # 生成树的点集
        ts_set = {}  # 生成树的边集

        s_set = sorted(s_set.items(), key=lambda v: (v[1], v[0]))  # 对边集进行排序

        v0 = v_set[0]  # 任取一点作为起始点
        tv_set.append(v0)
        ts_len = 0  # 加入边的数量

        print('生成过程：')
        print('起始点', v0)
        while True:
            for s in s_set:  # 遍历边集，每次找一条权值最小且相邻边
                s_name = s[0]
                s_weight = s[1]
                if s_name[0] in tv_set and s_name[1] in tv_set:  # 两个端点都在树中，形成了环，跳过
                    print('加入', s_name, '后，会形成环，跳过')
                    continue
                elif s_name[0] in tv_set:  # 边的端点和树相连
                    print('加入边', s_name)
                    tv_set.append(s_name[1])  # 加入树的点集
                    ts_set.update({s_name: s_weight})  # 加入树的边集
                    s_set.remove(s)
                    break
                elif s_name[1] in tv_set:  # 边的端点和树相连
                    print('加入边', s_name)
                    tv_set.append(s_name[0])  # 加入树的点集
                    ts_set.update({s_name: s_weight})  # 加入树的边集
                    s_set.remove(s)
                    break
            print('树中点集', tv_set)
            print('剩余边集', s_set)

            if ts_len == len(ts_set):  # 全部找完都没有新的边加入
                print('输入的图不连通')
                return

            ts_len = len(ts_set)
            if len(v_set) == len(tv_set):  # 图中的顶点数 = 树中顶点数
                break

        tree = [tv_set, ts_set]
        print('最小生成树为：')
        Output.print_graph_set(tree)
